public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public static TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public static boolean insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root==null){
            root=node;
            return true;
        }else{
            TreeNode cur=root;
            while(cur!=null){
                if(cur.key==key){
                    return false;
                }
                if(cur.key>key){
                    cur=cur.left;
                }else{
                    cur=cur.right;
                }
            }
            cur=root;
            while(cur.left!=null&&cur.right!=null){
                if(cur.key>key){
                    cur=cur.left;
                }else{
                    cur=cur.right;
                }
            }
            if(cur.key>key){
                cur.left=node;
                return true;
            }else{
                cur.right=node;
                return true;
            }

        }
    }
    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur=root;
        while(cur!=null){
            if(cur.key==key){
                return cur;
            }
            if(cur.key>key){
                cur=cur.left;
            }else{
                cur=cur.right;
            }
        }
        return null;

    }
    //删除key的值
    public static boolean remove(int key) {
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if(cur.key==key){
                removeNode(cur,parent);
                return true;
            }
            if(cur.key>key){
                parent=cur;
                cur=cur.left;
            }else{
                parent=cur;
                cur=cur.right;
            }
        }
        return false;
    }
    public  static  void removeNode(TreeNode cur,TreeNode parent){
        if(cur.left==null){
            if(cur==root){
                root=root.right;
            }else{
                if(cur==parent.left){
                    parent.left=cur.right;
                }else{
                    parent.right=cur.right;
                }
            }
        } else if (cur.right==null) {
            if(cur==null){
                root=root.left;
            }else {
                if(cur==parent.left){
                    parent.left=cur.left;
                }else{
                    parent.right=cur.left;
                }
            }
        }else{
                TreeNode targetParent=cur;
                TreeNode target=cur.left;//寻找替罪羊
                while(target.right!=null){
                    targetParent=target;
                    target=target.right;
                }
                cur.key=target.key;
                if(targetParent.left==target){
                    targetParent.left=target.left;
                }else if(targetParent.right==target){
                    targetParent.right=target.left;
                }
        }

    }

    public static void main(String[] args) {
        insert(8);
        insert(4);
        insert(12);
        insert(9);
        insert(13);
        remove(12);
        System.out.println("");
    }

   
}